package seminarski.geometrija;

import java.util.ArrayList;
import java.util.Collections;

import seminarski.utils.Utils;

import common.point.PointG;
import common.segment.SegmentG;

public class ConvexHull {
	private ArrayList<PointG<Double>> omotac;
	PointG<Double> minY, maxY;
	
	public ConvexHull(){
		omotac = new ArrayList<PointG<Double>>();
	}
	
	
	public boolean secePoligon(SegmentG<Double> duz){
		return false;
	}
	

	public double binarnaPretraga1(ArrayList<PointG<Double>> tacke){
		int n = tacke.size();
		int minIndex = minTacka(tacke);
		int maxIndex = maxTacka(tacke);
		int minIndex2 = minIndex + 1;
		minIndex2 %= n;
		SegmentG<Double> duz = new SegmentG<Double>(tacke.get(minIndex), tacke.get((minIndex2)% n));
		double k1 = (duz.p2().y() - duz.p1().y())/(duz.p2().x()  - duz.p1().x());
		double n1 = duz.p2().y() - k1 * duz.p2().x();
		double kn = -1/k1;
		double nn = tacke.get(maxIndex).y() - kn * tacke.get(maxIndex).x();

		double x =  ((k1 - kn)/(nn - n1));
		double y =  (kn*x + nn);
		PointG<Double> presecnatacka = new PointG<Double>(x, y);
		double distance1 = Utils.distance(presecnatacka, tacke.get(minIndex));
		
		double distance2 = distance1;
		do{
			distance1 = distance2;
			
			minIndex = minIndex + 1;
			minIndex %= n;
			maxIndex = maxIndex + 1;
			maxIndex %= n;
			minIndex2 = minIndex + 1;
			minIndex2 %= n;
		    duz = new SegmentG<Double>(tacke.get(minIndex), tacke.get((minIndex2)% n));
		    k1 = (duz.p2().y() - duz.p1().y())/(duz.p2().x() - duz.p1().x());
			n1 = duz.p2().y() - k1 * duz.p2().x();
			kn = -1/k1;
			nn = tacke.get(maxIndex).y() - kn * tacke.get(maxIndex).x();
			x = (long) ((k1 - kn)/(nn - n1));
			y = (long) (kn*x + nn);
			presecnatacka = new PointG<Double>(x, y);
			distance2 = Utils.distance(presecnatacka, tacke.get(minIndex));	
		}while(distance2 > distance1);
	
		return distance2;
	}

	
	public int maxTacka(ArrayList<PointG<Double>> tacke)
	{
		if(tacke == null)
			return -1;
		PointG<Double> maxPoint = tacke.get(0);
		int index = 0;
		for(int i = 0; i < tacke.size(); i++)
		{
			PointG<Double> point = tacke.get(i);
			if(point.y() > maxPoint.y()){
				maxPoint = point;
				index = i;
			}
			else if(point.y() == maxPoint.y() ){
				maxPoint = point.x() > maxPoint.x() ? point : maxPoint;
				index = point.x() > maxPoint.x() ? i : index;
			}
		}
		maxY = maxPoint;
		return index;
	}
	
	public int minTacka(ArrayList<PointG<Double>> tacke)
	{
		if(tacke == null)
			return -1;
		
		PointG<Double> minPoint = tacke.get(0);
		int index = 0;
		for(int i = 0; i < tacke.size(); i++)
		{
			PointG<Double> point = tacke.get(i);
			if(point.y() < minPoint.y()){
				minPoint = point;
				index = i;
			}
			else if(point.y() == minPoint.y()){
				minPoint = point.x() < minPoint.x() ? point : minPoint;
				index = point.x() < minPoint.x() ? i : index;
			}
		}
		minY = minPoint;
		return index;
	}
	
	public ArrayList<PointG<Double>> convexHull(ArrayList<PointG<Double>> tacke){
		omotac.clear();	
		maxTacka(tacke);
		omotac.add(maxY);
		tacke.remove(maxY);
		
		Collections.sort(tacke, new PointLComparator(maxY));
		omotac.add(tacke.get(0));
		int m = 1;
		for(int i = 1; i < tacke.size() ; i++)
		{
			omotac.add(tacke.get(i));
			if(Utils.vektorskiProizvod(omotac.get(m - 1), omotac.get(m), tacke.get(i)) <= 0){
				m++;
				continue;
			}
			else
			{
				while(Utils.vektorskiProizvod(omotac.get(m - 1), omotac.get(m), tacke.get(i)) >= 0){
					if(m == 1)
						break;
					else
					{
						omotac.remove(m);
						m--;
					}
				}
				m++;
			}
		}
		tacke.add(maxY);
		return omotac;
	}
	
	public int hullSize(){
		return omotac.size();
	}
	
	public ArrayList<PointG<Double>> getHull(){
		return omotac;
	}
		
	public PointG<Double> getMinY()
	{
		return minY;
	}
	
	public PointG<Double> getMaxY()
	{
		return maxY;
	}

	/**
	 * 
	 * @param point
	 * @return indeks <code>point</code> na omotacu
	 */
	public int getIndex(PointG<Double> point){
		return omotac.indexOf(point);
	}
	/**
	 * 
	 * @param i indeks tacke na omotacu
	 * @return i-ta tacka sa omotaca
	 */
	public PointG<Double> getPoint(int i) {
		return omotac.get(i);
	}


	public boolean pointOnAHull(PointG<Double> f) {
		for(int i = 0; i < omotac.size(); i++)
			if(f.x().doubleValue() == omotac.get(i).x().doubleValue() && f.y().doubleValue() == omotac.get(i).y().doubleValue())
				return true;
		return false;
	}

}
